651_Zelentsov_B.P._Matrichnye_modeli_funktsionirovanija_

2.9.ПРЕДЕЛЬНЫЕ ВЕРОЯТНОСТИ ЭРГОДИЧЕСКОГО МАРКОВСКОГО ПРОЦЕССА

Эргодический марковский процесс это такой марковский процесс, множество состояний которого образует одно эргодическое множество.

Понятие эргодического марковского процесса связано с предельными веро-

ятностями состояний. Предельной вероятностью j состояния wj эргодического марковского процесса называется вероятность нахождения в этом состоянии при t , то есть в далеком будущем. Предельная вероятность имеет тот же

смысл, что и для цепи Маркова: j есть средняя доля времени нахождения в со-

стоянии wj при t .

Синонимы: финальная вероятность, стационарная вероятность, равновесная вероятность.

Теорема о существовании и единственности предельных вероятностей.

Для эргодического однородного марковского процесса предельные вероятности существуют и не зависят от начального состояния, то есть

j = lim pij(t).

t

Теорема приведена без доказательства. Существование предельных вероятностей, не зависящих от начального состояния, строго доказано в специальной литературе.

Смысл теоремы: далекое будущее эргодического процесса не зависит от начального состояния.

Замечание. Иногда эргодический марковский процесс определяют через существование предельных вероятностей: марковский процесс называется эргодическим, если для всех состояний существуют отличные от нуля предельные вероятности состояний, образующих полную группу событий:

lim pij(t) = j,	j = 1.
t	j

Вероятности pij(t) и предельные вероятности j описывают разные режимы эргодического марковского процесса: переходный (нестационарный) режим и установившийся (стационарный) режим. В переходном режиме вероятности состояний зависят от времени, ввиду чего характеристики системы в этом режиме также зависят от времени. А в установившемся режиме, то есть при достаточно долгом протекании процесса, вероятности состояний перестают зависеть от времени, ввиду чего характеристики системы также перестают зависеть от времени. Таким образом, для эргодического марковского процесса можно рассматривать как переходный, так и установившийся режимы.

31

Поскольку предельные вероятности эргодического марковского процесса j не зависят от начального состояния, то они не зависят и от начального распределения:

lim

p

(t)

π

,

(2.10)

t

где

π

= 1 2

3

… m – распределение предельных вероятностей в виде

строки (вектора). Действительно, если

p

(t) =

p

(0)P(t),

то

p(0) lim P(t)= p(0)· = π, t

где – матрица, каждая строка которой является предельным распределением π.

Теорема о связи предельных вероятностей и интенсивностей перехода. Для эргодического однородного марковского процесса выполняется условие:

где

o

– нулевая строка.

π

· =

o

,

(2.11)

Доказательство.

Система дифференциальных уравнений

А.Н. Колмогоро-

ва в матричном виде:

p

(t) =

p

(t) . При

t вероятности

pj(t) стремятся к

предельным, поэтому

lim p(t) π и lim

p (t) = o , откуда π = o .

t

t

Теорема доказана.

Замечание. Распределение π называют также финальным, стационарным, предельным, инвариантным; иногда его называют еще неподвижным вектором матрицы Λ.

Смысл теоремы. Матричное уравнение (2.11) представляет собой однородную систему линейных алгебраических уравнений относительно неизвестных

j. Число неизвестных равно числу уравнений системы.

Система уравнений является неопределенной, имеет бесконечно много решений, так как на систему наложена одна зависимость: сумма элементов любой строки матрицы равна нулю. Поэтому ранг матрицы на единицу меньше

числа неизвестных. Добавив независимое условие нормированности 1 + 2 +

3 + … = 1, получим определенную систему, имеющую единственное решение. Такую систему можно решить, например, методом Гаусса или Крамера.

2.10. ВЫЧИСЛЕНИЕ ПРЕДЕЛЬНЫХ ВЕРОЯТНОСТЕЙ

Приведем две формулы для вычисления предельных вероятностей эргодического марковского процесса.

Первая формула основана на обращении матриц:

			π j	1			,		(2.12)
						1
				1 λ j j e
где	j матрица, полученная из исходной матрицы вычеркиванием j-й стро-
ки и	j-го столбца;		j j-я строка матрицы без элемента					jj;	e столбец, все
элементы которого равны 1.
				32

Исходным уравнением для вывода этой формулы является равенство (2.11).

Запишем это равенство, выделив в нем состояние wj:

					λ	jj	λ j
	π j	π j						o ,
					λ j		j

где λ j – j-й столбец матрицы без элемента jj; π j – строка предельных веро-

ятностей без элемента j. После умножения строки на матрицу получаем новую строку:

·

+

π

·λ

·

+

π

·

=

o

.

jj

j

j

λ

j

j

j

j

j

1

Отсюда имеем равенство π j· j

= – j ·λ j или

π j = – j ·λ j · j

. Умножим

это выражение на столбец e справа, все элементы которого равны 1, что приво-

дит к суммированию элементов строк: π j·e= – j ·λ j · j1·e. Прибавим к левой

					1
и правой части вероятность j: π j·e			+ j = j – j ·λ j · j			·e. С учетом условия

нормированности имеем: π j·e + j = 1. Поэтому j (1– λ j · j1·e ) = 1, откуда получаем формулу (2.12): π j 1/(1 λ j j1 e).

По формуле (2.12) вычисление каждой предельной вероятности j связано с вычислением обратной матрицы, порядок которой на единицу меньше порядка исходной матрицы.

Замечание. Размеры перемножаемых матриц в формуле (2.12) согласованы. Вторая формула основана на вычислении определителей:

π j		j				det j	,	(2.13)
	m					m
			k			det k
	k 1					k 1

j = det j – определитель матрицы j.

По формуле (2.13) предельные вероятности можно вычислить только после вычисления всех определителей и нахождения их суммы.

На практике возможно использовать комбинацию из этих формул. Поскольку предельные вероятности состояний пропорциональны соответствующим определителям, то можно вычислять предельные вероятности состояний без вычисления суммы определителей:

	πk	det k	πi,	(2.14)
		det i

где i – известная предельная вероятность i-го состояния, вычисленная, напри-

мер, с помощью обращения матрицы по формуле ( 2.12 ), а k – предельная вероятность любого другого состояния.

33

Таким образом, матрица интенсивностей эргодического однородного марковского процесса достаточна для нахождения предельных вероятностей.

Следует отметить, что операции по вычислению предельных вероятностей можно выполнять с помощью таких современных инструментов, как Mathcad

или Mathlab.

Замечание. Переходный и установившийся режимы имеют место также и для однородной цепи Маркова.

2.11.ВЫВОДЫ

1.Переходы между состояниями однородного марковского процесса описы-

ваются интенсивностями переходов, которые удобно записывать в виде матрицы интенсивностей.

2.Вероятности состояний однородного марковского процесса являются решениями системы обыкновенных линейных однородных дифференциальных уравнений.

3.Система дифференциальных уравнений может быть составлена в матричной форме или по графу состояний в соответствии с приведенным правилом при заданном начальном состоянии.

4.При решении матричного дифференциального уравнения операторным

методом нужно выполнять обращение функциональной матрицы (sE ) и пользоваться формулами обратного преобразования Лапласа.

5.Для эргодического однородного марковского процесса имеют место переходный и установившийся режимы.

6.Для нахождения вероятностей состояний в переходном режиме необходимы начальное распределение вероятностей состояний и матрица интенсивностей.

7.Матрица интенсивностей достаточна для нахождения предельных вероятностей состояний эргодического марковского процесса в установившемся режиме.

8.На основе приведенного матричного метода можно строить аналитические и алгоритмические модели эксплуатации и функционирования оборудования телекоммуникационных систем. В частности, этим методом могут быть найдены вероятностные характеристики этих систем путем вычисления вероятностей состояний в переходном и стационарном режимах. Операции с матрицами целесообразно выполнять на базе современных программных инструмен-

тов типа Mathcad и Mathlab.

34

2.12. ПРИМЕР МАРКОВСКОГО ПРОЦЕССА С ТРЕМЯ СОСТОЯНИЯМИ

Дан марковский процесс с тремя состояниями, граф состояний которого приведен на рис. 2.3. На графе обзначены интенсивности переходов между состояниями. Ограничимся вычислением предельных вероятностей состояний.

2

w1

μ3

1

μ1

3

w2 w3

Рис. 2.3. Граф состояний марковского процесса с тремя состояниями

Матрица интенсивностей имеет вид:

	(λ	μ )	μ	λ
	1	1	1	1
=	λ2		λ2	0	.
	μ3		λ3
				(λ3 μ3)

Замечание. После составления матрицы переходных вероятностей целесообразно сделать проверку условия | | = 0.

Подматрицы i, в которых вычеркнуты i-я строка и i-й столбец, и определители этих подматриц:

				=	λ			2		0		;	|					| = λ ·λ + λ ·μ ;
			1													1
							λ3													2	3	2	3
									(λ3 μ3)
		(λ			μ )					λ			|				| = λ ·λ + λ ·μ + μ ·μ ;
	2	=		1			1			1	;				2
				μ3															1		3	3	1 1 3
									(λ3 μ3)
							=		(λ	μ )	μ	1		;				|		| = λ ·λ .
						3			1	1									3
									λ2												1	2
											λ2

Сумма определителей:

= | 1| + | 2| = | 3| = λ1·λ2 + λ1·λ3 + λ2·λ3 + λ3·μ1 + λ2·μ3 + μ1·μ3.

Предельные вероятности, вычисленные по формуле (2.13):

1 = | 1|/Δ = (λ2·λ3 + λ2·μ3)/Δ; 2 = | 2|/Δ = (λ1·λ3 + λ3·μ1+ μ1·μ3)/Δ;3 = | 3|/Δ = λ1·λ2/Δ.

Строки матрицы без элементов ii:

	1= μ1	λ1 ;	λ	2 = λ2	0 ;	λ	3= μ3	λ3 .
λ

Подставив подматрицы i и строки λi в формулу (2.12), получим те же вы-

ражения для предельных вероятностей 1, 2, 3.

35

Придадим интенсивностям переходов следующие значения:

λ1 = 0,01; λ2 = 0,02; λ3 = 0,03; μ1 = 0,04; μ3 = 0,05.

Значения определителей подматриц i и суммы определителей:

| 1| = 0,0016; | 2| = 0,0035; | 3| = 0,0002; = 0,0053.

Значения предельных вероятностей, вычисленные по приведенным формулам:

1 = 0,302; 2 = 0,660; 3 = 0,038.

Замечание. Видно, что во всех случаях 1 + 2 + 3 = 1.

36

Глава 3. ПОЛУМАРКОВСКИЕ ПРОЦЕССЫ

3.1. ПОНЯТИЕ ПОЛУМАРКОВСКОГО ПРОЦЕССА

Для моделирования сложных систем часто используют методы, основанные на полумарковских процессах. Идея полумарковских процессов (или идея вложенных цепей Маркова заключается в том, что выбирают моменты времени, в которых процесс, описывающий эволюцию системы во времени, образует однородную цепь Маркова. Полумарковский процесс задается последовательны-

ми состояниями w1, w2, … В момент перехода wi wj «забывается» все прошлое, а дальнейшая эволюция определяется только состоянием в момент перехода.

Отличие полумарковского процесса от марковской цепи и марковского процесса состоит в том, что переходы рассматриваются не на шагах и не во времени, а в моменты выхода из состояний (или моменты смены состояний). Эти моменты могут быть как случайными, так и детерминированными.

Полумарковский процесс является более общим математическим понятием по сравнению с цепью и процессом Маркова.

Процесс смены состояний на дискретном множестве W задается вероятностями pij , которые названы вероятностями прохождений. Вероятность прохож-

дения pij – это условная вероятность того, что при перемене состояния wi сис-

тема перейдет в состояние wj, то есть pij – это условная вероятность

непосредственного перехода wi → wj при условии, что состояние wi меняется. Поскольку вероятности pij описывают процесс только в момент перемены со-

стояния, то pii = 0 для всех wi.

Вероятности прохождений не содержат информации о продолжительности состояний. Если такие характеристики нужны для моделирования системы, то их задают совместно с вероятностями прохождений. Продолжительности состояний можно задавать средними значениями числа шагов или времени нахождения в состояниях после попадания в них.

Как и в случае цепи и процесса Маркова, полумарковский процесс изображают в виде ориентированного графа, вершинами которого являются состояния, а ребрами – переходы между состояниями. Каждому переходу приписана соответствующая вероятность прохождения, а каждому состоянию – среднее число шагов или среднее время нахождения в нем после однократного попадания в это состояние.

Классификация состояний сохраняется такой же, как для цепей и процессов Маркова.

37

Вероятности pij полумарковского процесса могут быть найдены для про-

цессов в непрерывном времени при произвольных распределениях времени событий и переходов между состояниями. При такой замене переходят от процесса в непрерывном времени к процессу в дискретном времени. В данной главе рассмотрено формирование полумарковского процесса на основе цепи Маркова и процесса Маркова.

3.2.ФОРМИРОВАНИЕ ПОЛУМАРКОВСКОГО ПРОЦЕССА НА ОСНОВЕ ЦЕПИ МАРКОВА

Рассмотрим переход от цепи Маркова к полумарковскому процессу.

Пусть состояние wi является начальным, а pij – переходная вероятность цепи Маркова wi wj . Найдем вероятность прохождения pij . Обозначим через qij

(n) вероятность непосредственного перехода wi wj на n-м шаге. Естественно допустить, что состояние wi является начальным, то есть

qii (0) = 1. Очевидно:

на первом шаге: qij (1) = qii (0) pij = pij; на втором шаге: qij (2) = qii(1) pij= pii pij; на третьем шаге: qij (3) = qii (2) pij = pii2 pij;

на четвертом шаге: qij (4) = qii (3) pij = pii3 pij;

на произвольном n-м шаге: qij (n) = qii (n – 1) pij = piin 1 pij.

Непосредственный переход может быть на любом шаге, поэтому искомая вероятность есть сумма приведенных вероятностей, поскольку описанные переходы несовместны:

							pij
	pij = qij(n) = pij (1 + pii + pii2 + pii3+ … + piin + …) =							.
	n 1						1 pii
	Итак, вероятность прохождения wi wj
			pij
	pij			,	i j;	pii= 0.	(3.1)
			1 pii

Видно, что вероятность прохождения wi wj пропорциональна переходной вероятности pij.

Примечание. Если переходная вероятность pij = 0, то также и вероятность прохождения pii = 0.

Среднее число шагов нахождения в состоянии после попадания в него най-

дено в разделе 1.4: θii(n) = 1/(1– pii).

38

3.3.ФОРМИРОВАНИЕ ПОЛУМАРКОВСКОГО ПРОЦЕССА НА ОСНОВЕ ПРОЦЕССА МАРКОВА

Рассмотрим переход от марковского процесса к полумарковскому. Марков-

ский процесс задан графом состояний и интенсивностями переходов ij в непрерывном времени.

Обозначим через qij(t) вероятность непосредственного перехода wi wj в

течение времени t. Рассмотрим переход wi wj на интервале [0, t + dt]. Оче-

видно: qij(t + dt) = qij(t) + qii(t)· ij·dt, так как переход wi wj на интервале времени [0, t + dt] является суммой двух несовместных событий: перехода на интервале [0, t] и перехода на интервале [t, t + dt]. Последнее событие является

произведением двух событий: на интервале [0, t] переход wi wj не произошел, а произошел на интервале [t, t + dt].

Известно, что qii(t) = exp( iit), где ii – суммарная интенсивность выхода из состоянии wi, взятая с обратным знаком (см. раздел 2.4). Преобразуем получен-

ное уравнение и подставим в него qii(t):

q ij(t) = ij exp( iit), i j,

Проинтегрируем это уравнение: qij(t) = ij exp( iit) + c.

ii

	Найдем c из начального условия qij(0) = 0: 0 =			ij	+ c, откуда	c =	ij	.
				ii			ii
	Итак, искомая вероятность
		ij
	qij(t) =		(1 exp( iit)), i j.					(3.2)
		ii

Видно, что вероятность qij(t), i j, состоит из двух множителей:

1)постоянного множителя ij ;

ii

2)переменного множителя 1 exp( iit), который представляет собой вероят-

ность того, что в течение времени t состояние wi изменится.

Видно также, что вероятности qij(t) являются возрастающими для ij 0 и

	lim qij(t) =		ij	, i j, ij 0.	(3.3)
			ii
	t
	Замечания. 1. Если ij	= 0, то непосредственный переход wi wj является

невозможным и qij(t) = 0.

2. Вероятности qij(t) не являются функциями распределения времени пере-

хода между двумя состояниями, так как lim qij(t) 1. t

39

Просуммируем вероятности qij(t) по всем j:

ij

1 exp

t =

q

(t) +

q

(t) = exp(

t) +

ii

ij

ii

ii

j, j i

j, j i

ii

	1 exp( iit)						1 exp( iit)
				ij
= exp( iit) +						= exp( iit) +		ii	=
	ii						ii
				j, j i

= exp( iit) + 1 exp( iit) = 1.

Таким образом, события, вероятности которых просуммированы, образуют полную группу событий.

Итак, описан переход от марковского процесса в непрерывном времени к полумарковскому процессу. Случайный процесс в непрерывном времени фор-

мально представлен в дискретном времени. Вероятности прохождений wi wj

пропорциональны интенсивностям перехода ij:

		λij
	pij		,	i j; pii = 0.	(3.4)
		λii

Средние времена нахождения в состояниях выражаются в единицах непрерывного времени (см. раздел 2.4): θii(t) = – 1/ ii.

3.4.ИСХОДНЫЕ МАТРИЧНЫЕ ХАРАКТЕРИСТИКИ ПОЛУМАРКОВСКОГО ПРОЦЕССА

Матричной характеристикой переходов между состояниями полумарковского процесса является матрица вероятностей прохождений P = pij .

Для эргодического полумарковского процесса матрица P является стохастической. Эта матрица удовлетворяет следующим условиям:

1)все элементы матрицы неотрицательны;

2)диагональные элементы равны нулю;

3)сумма элементов любой строки равна 1;

4)в каждой строке имеется хотя бы один ненулевой элемент;

5)в каждом столбце имеется хотя бы один ненулевой элемент.

Средние времена нахождения в состояниях задают с помощью матриц

(n)

(n)

,

(t)

(t)

(n)

(n)

(t)

(t)

(n)

и

= θii

= θii

или столбцов θ

= θi

, θ

= θi

, где θii

θii(t) – соответственно среднее число шагов и среднее время нахождения в со-

стоянии wi при однократном попадании в него; θij(n) = 0, θij(t) = 0, если i j.

Если полумарковский процесс сформирован на основе однородной цепи Маркова, то матрица вероятностей прохождений выражается через матрицу переходных вероятностей следующим образом:

P = pij = (E – Pdg)–1·(P – Pdg).	(3.5)
40